数据结构递归题

先来理解一下递归

先写一个会导致堆栈溢出的例子：

def countdown(i):
  print i
  countdown(i - 1)

编写递归是必须告诉它何时停止递归。正因此，每个递归都有两个条件：

基线条件（base case）
递归条件（recursive）

递归条件指的是函数调用自己，而基线条件是则是指的函数不再调用自己，从而避免无限循环

再来给上面的死循环加上基线条件

def countdown(i):
  print i
  if i <= 1         # 基线条件
    return
  else :            # 递归条件
    countdown(i - 1)

回溯算法解迷宫问题

以一个 M × N 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计程序，对任意设定的迷宫，求出从入口到出口的所有通路。

该图是一个迷宫的图。1 代表是墙不能走，0 是可以走的路线。只能往上下左右走，直到从左上角到右下角出口。

做法是用一个二维数组来定义迷宫的初始状态，然后从左上角开始，不停的去试探所有可行的路线，碰到 1 就结束本次路径，然后探索其他的方向，当然我们要标记一下已经走的路线，不能反复的在两个可行的格子之间来回走。直到走到出口为止，算找到了一个正确路径。

先生成一个迷宫

/**
 * 迷宫问题
 *
 * @author alsritter
 * @version 1.0
 **/
public class MiGong {
    public static void main(String[] args) {
        // 先创建一个二维数组，模拟迷宫
        int width = 7;
        int height = 8;

        int[][] map = {
                {1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 0, 0, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1}
        };

        // 输出地图
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                System.out.printf("%d ", map[i][j]);
            }
            System.out.println();
        }
    }
}

输出：

1 1 1 1 1 1 
0 0 0 0 0 1 
0 0 0 0 0 1 
1 1 1 0 0 1 
0 0 0 0 0 1 
0 0 0 0 0 1 
0 0 0 0 0 1 
1 1 1 1 1 1

深度搜索的方式（DFS）

注意：这个和 “填色算法” 大同小异，本质都是深度搜索

然后编写寻路的递归算法：

    /**
     * 找路，这里约定 1 表示墙，0 表示路，2 表示当前找到的路径；3 表示该点已经走过了，但是走不通
     * 在走迷宫时，需要确定一个策略（方法）：下->右->上->左，如果该点走不通再回溯
     * 
     * @param map     地图
     * @param startX  起始位置
     * @param startY  起始位置
     * @param targetX 目标位置
     * @param targetY 目标位置
     */
    public static boolean check(int[][] map, int startX, int startY, int targetX, int targetY) {
        // 道路已经找到了（退出条件）
        if (map[targetY][targetX] == 2) {
            map[targetY][targetX] = 9; // 将其标识为特别的数字方便查看
            print(map); // 打印地图
            return true;
        }

        // 如果当前这个点还没有走过
        if (map[startY][startX] == 0) {
            // 按照策略 下->右->上->左
            map[startY][startX] = 2; // 先假定这个点是可以走的
            
            // 注意：这里的每一个 check 都会执行（因为它自己就是判断条件），
            // 说白了就是让 check 方法执行到这条路的尽头
            // 先向下走
            if (check(map, startX, startY + 1, targetX, targetY)) return true;
            // 向右走
            else if (check(map, startX + 1, startY, targetX, targetY)) return true;
            // 向上走
            else if (check(map, startX, startY - 1, targetX, targetY)) return true;
            // 向左走
            else if (check(map, startX - 1, startY, targetX, targetY)) return true;
            // 上面的 check 都不通过，说明该店是走不通的，是死路
            else {
                map[startY][startX] = 3;
                return false;
            }
        } else {
            // 如果 map[startY][startX] != 0 说明该点可能是 1、2、3
            return false;
        }
    }


    /**
     * 打印地图
     */
    private static void print(int[][] map) {
        int height = map.length;
        int width = map[0].length;

        // 输出地图
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                System.out.printf("%d ", map[i][j]);
            }
            System.out.println();
        }
    }

测试

 初始状态
1 1 1 1 1 1
0 0 0 0 0 1
0 0 0 0 0 1
1 1 1 0 0 1
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 0 0 1
1 1 1 1 1 1

 右下角 5, 6
1 1 1 1 1 1
2 0 0 0 0 1
2 2 2 2 0 1
1 1 1 2 0 1
0 0 0 2 0 1
0 0 0 2 0 1
0 0 0 2 9 1
1 1 1 1 1 1

 坐标 1, 4（就是墙的正下面）
1 1 1 1 1 1
2 3 3 3 3 1
2 2 2 2 3 1
1 1 1 2 3 1
9 2 2 2 3 1
2 2 2 2 3 1
2 2 2 2 3 1
1 1 1 1 1 1

球和篮子

你有几个同样的球，你希望把它放到几个篮子里。每个篮子有相同的容量。

给出 int 型的 baskets，代表篮子的数量。
给出 int 型的 capacity，代表每个篮子的最大容量。
给出 int 型的 balls，表示归类到篮子里的球的数量。

返回值是把球归类到篮子里的方式的数量。如果不能完全存放到篮子中，无法划分，返回0。

篮子互不同，所有的球相同。因此，如果 2 个球放到 2 个篮子里，你可以采用 3 种方式，即 (0, 2), (1, 1), 或 (2, 0)

Reference

回溯算法解迷宫问题

回溯算法解迷宫问题​

深度搜索的方式（DFS）​

球和篮子​

Reference​

回溯算法解迷宫问题

深度搜索的方式（DFS）

球和篮子

Reference